\documentclass[11p]{article}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{fullpage}
\usepackage{amsthm}
\usepackage{setspace}
\usepackage{subfigure}
\usepackage{comment} 
\usepackage{graphicx}
%\doublespacing
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
%\titleformat{\subsection}[runin]{\normalfont\normalsize\bfseries}{}{}{}
\begin{document}

\title{ Navigability on Networks: A Graph Theoretic Perspective }
\author{
 	Rishi Ranjan Singh\\
 	Department of Computer Science\\
	 Indian Institute of Technology Ropar \\
  	 \texttt{rishirs@iitrpr.ac.in}\\ \and
  	Shreyas Balakuntala\footnote{Intern}\\	
  	 Department of Computer Science\\
	 Indian Institute of Technology Ropar \\
   	\texttt{shreyasbs1@yahoo.com}\\ \and
 	 Sudarshan Iyengar\\
  	Department of Compute Science\\
 	Indian Institute of Technology Ropar \\
 	\texttt{sudarshan@iitrpr.ac.in}  
}
\maketitle

\begin{abstract}
Closeness centrality is a measure of the importance of a node in a network based on its distance relative to the other nodes. It has a widespread importance in the network analysis and navigation in networks. We introduce the concept of \textit{center-strategicness} to find the paths in a network passing through centrally located nodes. An application of the same would be in locating a hospital in a city ensuring that it is situated in a place that is centrally accessible from all major localities in the city. People are inclined to learn landmarks when they are asked to navigate from a source to destination. It is noted that these landmarks are nodes that have high closeness-centrality ranking (S.Iyengar et.al 2012 \cite{f}). A \textit{center-strategic path} is one in which, the plot of closeness centrality ranking of the vertices involved in it, has at-most one minima. A graph $G$ is \textit{center-strategic} if every pair of vertices in it has atleast one center-strategic path between them. We show that all graphs are not center-strategic and give counter examples to support the claim. We design a polynomial time algorithm to check if a graph is center-strategic or not. Hence, we show that navigability on a network is a decision problem which belongs to the $class-P$. We investigate the presence of center-strategic paths in Erdos-Renyi Graphs. Also, we prove that all Trees and Grids are center-strategic.
\end{abstract}

\section{ Introduction }
The idea of centrality was introduced by Alex Bavelas \cite{a} in 1948. In his paper, he considers structures which consist of cells connected to each other. He defines a measure of importance of a cell based on its distance from other cells in the structure. Studies on Centrality have been described by Harold Leavitt \cite{b}. A detailed examination of centrality in social networks has been done by Freeman \cite{c}. He uncovers all the conceptions of the centrality measure and also refines the then existing measures.
%
Closeness-centrality is defined as $c_C : V \rightarrow \mathbb{R}$, with {\footnotesize $c_C(v)=1/(\sum\limits_{u \in{V}}{d(u,v)})$}. The vertex with a very high $c_C$ value should be central in the graph (topologically) whereas a vertex with very low $c_C$ value must be in the periphery of the network and is hence less central. Computing closeness centrality involves the knowledge of the \textit{distance matrix} of the graph. Computation of this matrix by algebraic/combinatorial methods is polynomial in $n$. However for large $n$, these are impractical. An efficient way in which top few vertices of high closeness centrality can be computed is presented in \cite{d}. Eppstein and Wang in \cite{e} report an approximation
algorithm to compute closeness centrality.\\

Sudarshan et.al, introduces the concept of Center-strategic path in \cite{f}. They prove that humans prefer such paths over others while navigating from a source to a destination. Navigating from source to a given destination in a network with only local information is extensively studied. In the small world experiment by Milgram \cite{j}, letters from Nebraska are sent to Boston. This is one-way random walk, whereas Vijesh et.al., in \cite{h} considers two-way random walks where both sender and reciever takes random walks until both of them meet at a node. They give emperical results which show that 80\% of these paths from a source to a destination are center-strategic. 
\subsection{Motivation}
When humans are made to navigate from a source to a given destination, they tend to learn the network with the help of its landmarks. These landmarks are found to be nodes with high closeness centrality values (S.Iyengar et.al \cite{f}). Here, the participants will only have the local information about the network, i.e the participants can only view the nodes which are adjacent to the node they are currently on. When this experiment is repeated for different source and destination nodes, it is found that participants navigate along the paths which are \textit{center-strategic}. A path is said to be center-strategic when a participant moves towards a node with high \textit{closeness-centrality} value and then moves away from it to a node with less closeness-centrality value. Hence, it is shown that humans prefer to use paths which are center-strategic in nature. When these landmark nodes are removed, participants tend to find the new landmark nodes (Ramesh. A et.al \cite{g}).  In other words, there is an increase in performance of the learning strategy when obstacles are introduced.

Vijesh et.al \cite{h} presents a new algorithm which takes 2-way random walks in networks.  It is found that when robots are programmed to take random walks in a Scale-free network using the algorithm, the robots learn the network using its landmarks and also 80\% of the paths they navigate are found to be center-strategic. Dragan et.al \cite{i} proposes a novel way to navigate in the network using its spanning tree metric. In this paper, they reduce the navigation problem on a graph $G$ to that of its spanning tree $T$ and navigate on $T$.  They prove that spanning trees of Grids are \textit{optimal-carcasses} and hence prove grids to be navigable.

In this paper, we define \textit{navigability on a network} and hence determine whether the given network is \textit{navigable} or not. We see navigability on networks as a decision problem and prove that it belongs to \textit{class-P}. With the help of thorough graph theoretic analysis, we prove that trees and grids are always navigable.
\subsection{Previous work}
Humans adopt learning strategies when asked to navigate in an environment which is unknown to them. To understand how humans explore a complex environment, Moeser \cite{gg} conducted an experiment and observed how nurses learned to navigate in a hospital building which had a very complex structure. He discovered that the nurses preferred lorger routes which are easy to remember over the shorter ones. Aginsky et al., \cite{aa} proposed two such strategies which are visually dominated and spatially dominated. Human navigation is extensively studied as a topic in spatial cognition for quite some years now \cite{aa,bb,cc,dd}. Basakya et al,. \cite{ee} explains the wayfinding mechanism of newcomers in an unfamiliar environment. When it comes to wayfinding, one learns whatever is necesssary and sufficient to achieve the goal \cite{ff}.
\subsection{Definitions}
\textbf{Closeness Centrality: }
%The centrality measure which ranks vertices based on its distance from the other vertices is called the\\
 \textit{Closeness Centrality} is defined as $c_C : V \rightarrow \mathbb{R}$, with {\footnotesize $c_C(v)=1/(\sum\limits_{u \in{V}}{d(u,v)})$}. The vertex with a very high $c_C$ value should be central in the graph (topologically) whereas a vertex with very low $c_C$ value must be in the periphery of the network and is hence less central. For notational convenience, we define $C(v)$ as the reciprocal of closeness centrality of a vertex $v$, i.e. 
$C(v)=\frac{1}{c_C(v)•}$.\\
\textbf{Center-strategic path: }
We define \textit{center-strategic path} as a path $( v_1, v_2, \cdots ,v_k )$ such that the plot of $( c_C(v_1), c_C(v_2), \cdots , c_C(v_k) ) $ has at most one minima.\\
\textbf{Center-strategic pair: } In a graph, a vertex pair $(u,v)$ is called as center-strategic pair (CSP) if there exists atleast one center-strategic path between these pair of vertices in the graph. \\
\textbf{Center-strategicness of a Graph: }
A graph $G(V,E)$ is \textit{center-strategic} if every possible pair of vertices of the graph, $(u,v)$ is a CSP, where $u, v \in V $ .\\
\textbf{Navigability on Graphs: }
We say a graph $G$ is navigable, if it is center-strategic. To check if a graph is center-strategic or not is exponential, since all the paths between between given 2 nodes is exponential.
To quantify \textit{Navigability}, we use the concentration of center-strategic pairs, i.e. number of vertex pairs between which there exists atleast one center-strategic path out of all ${n}\choose{2}$ combinations.\\

\subsection{Brief overview of our results}
In this paper, we present a polynomial time algorithm which returns True if the input graph is center-strategic or False otherwise. Hence, we show that \textit{Navigability on Networks} is a decision problem which belongs to class-P.
We investigate the presence of Center-strategic paths in Erdos-Renyi graphs \cite{er} and present some experimental results. If an ER graph is not center-strategic, then we find the concentration of center-strategic pairs in the graph. We prove Trees and Grids to be center-strategic always. In addition, for trees, we prove that the there are atmost two top closeness centrality ranked vertices  and the path between any two vertices is center-strategic. 
 
\section{Results}All the graphs considered in the literature are connected, undirected and unweighted. The algorithm defined in the next section can be used for checking the navigability of edge weighted graphs also. After describing the concept of measuring the navigability in a graph by closeness centrality of nodes in the graph, we will analyze this concept on various special graphs. First, we will analyse general graphs and then extend the analysis to other graphs. Here we present a polynomial time heuristic for checking the navigability of a graph. Then we will see the experimental results on Erdos-Renyi graphs by implementing the algorithm. Experimental results for Erdos-Renyi graphs also remain valid for general graphs. We also work on trees and grids and prove that both categories of graphs are always easily navigable. So lets start with the general graph. Next we will show that all graphs are not center-strategic i.e. all graphs are not easily navigable.
\subsection{On General Graphs}
\begin{theorem}
All graphs are not center-strategic.
\end{theorem}
\begin{proof}
We prove the theorem by giving a counter example. Given below is a graph $G=(V,E)$ with $|V|=5$. $G$ is a complete bipartite graph and $V=A\cup B$, where $A$ and $B$ are the bi-partition sets such that $A\cap B=\phi$, $|A|=3$ and $|B|=2$. After evaluating the closeness centrality of all the nodes, we see that the nodes in the set $B$ are making a non center-strategic pair. So, all the graphs are not center-strategic and hence not easily navigable as per the concept.
\begin{figure}[H]
\begin{center}
\includegraphics[width=3cm, height=4cm]{im.jpg}
\end{center}
\caption{{ A complete bipartite graph $K_{(3,2)}$. All the edges in the graph are unweighted. Closeness centrality of vertices are labeled on it. Vertex pair in set B is making the graph non center-strategic.}}
\end{figure}
\end{proof}
We observe that $K_{(3,2)}$ is the smallest non center-strategic graph. It can be easily proved as all the connected graphs with atmost 4 nodes are always center-strategic. With 5 nodes $K_{(3,2)}$ is the only possible structure showing non center-strategicness.    
\begin{theorem}[Conjecture]
All non center-strategic graphs contain atleast one $K_{(3,2)}$ complete bipartite graph as an induced subgraph with some additional constraints.  
 \end{theorem}
Suppose that we are checking the center-straegicness of the graph $G$. Then the conjecture can be stated in detail as; \textit{Graph $G$ will be non center-strategic iff there exists a $K_{(3,2)}$ induced subgraph $H$ and let $u_1$ and $u_2$ are the vertices in $H$ with degree $3$ and $v_1, v_2$ and $v_3$ are the vertices with degree $2$ such that these vertices hold the following properties:
\begin{enumerate}
\item One of the vertices, $u_1$ or $u_2$ will be the highest degree vertex in the original graph $G$.
\item Other one will be the second highest degree vertex until there exists other $K_{(3,2)}$ as induced subgraph and candidature for making graph non center-strategic.
\item Degree of $v_i$, for $i=1,2,3$ will always be lower than the degree of any $u_j$, $j=1,2$. 
\end{enumerate} } 
In the above case $u_1$ and $u_2$ will make non center-strategic pair in the graph.
In verifying whether a graph is center-strategic or not, we need to verify for each pair of vertices, whether there exists a center-strategic path between them. Now for checking a center-strategic path between any pair of vertices, we may have to check all possible paths between them which can be exponential in number. So it seems that our verification process will take exponential time. It also gives an intuition that between a pair of vertices, there may exist exponential number of center-strategic paths. But the theorem given below proves that this problem still exists in the polynomial class $P$. So next we will give a polynomial time heuristic to check the navigability of the graph based on the center-strategicness. 
\begin{theorem}
There exists a polynomial time algorithm for verification of the center-strategicness of a graph. 
\end{theorem} 
\begin{proof}
We will describe an algorithm and then by the analysis of the algorithm, we prove that the algorithm runs in polynomial time and does not miss any point. The algorithm calls a procedure BFS\_C which is a variation of Breadth First Search algorithm (BFS). BFS is a well known traversal algorithm in a graph after its introduction by Moore in 1959 \cite{k}.  
\begin{algorithm}
\caption{Center-Strategicness of a Graph}
\label{alg:GS}
\begin{algorithmic}[1]
\REQUIRE Graph $G=V,E$ as input.
\STATE Set $Flag=True$.
\FOR{ all distinct pairs $(u,v)\in V\times V$ such that $u\neq v$} 
\STATE Run BFS\_C($u$) and store the results in the list $X$.\\
\STATE Run BFS\_C($v$) and store the results in the list $Y$.\\
\IF{$|X\cap Y|=\phi$}
\STATE Set $Flag=False$ and break the loop.
\ENDIF
\ENDFOR
\IF{$Flag==False$}
\STATE Output that "graph G is not center-strategic".
\ELSE
\STATE Output that "graph G is center-strategic"
\ENDIF
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\caption{BFS\_C}
\label{alg:GS}
\begin{algorithmic}[1]
\REQUIRE Graph $G=(V,E)$, $c_C:V\rightarrow R$ and $x\in V$ as input.
\STATE Run a restrictive variation of Breadth First Search algorithm where we call a node $q$ to be valid adjacent to $p$ in the graph if $(p,q)\in E$ and $c_C(p)\leq c_C(q)$.
\STATE Return the list of nodes reachable with valid adjacency from node $x$.
\end{algorithmic}
\end{algorithm}\\
\begin{lemma}Algorithm 1 finds all possible center-strategic paths between any pair of vertices in the graph.
\end{lemma} 
\begin{proof}
Suppose that we are given a graph $G=(V,E)$ and we are checking the center-strategicness between a pair of vertices $(u,v)$, where $u,v\in V$. So according to the algorithm, we calculate the list of nodes reachable in a restricted manner from node $u$ and $v$ separately by calling the procedures BFS\_C($u$) and BFS\_C($v$) . The restricted manner of reachability in procedure BFS\_C defined as a node $q$ is reachable to a node $p$ iff there exists a path P=\{$p_1, p_2, \cdots, p_k$\} such that $p_1=p$, $p_k=q$ and if $i\leq j$ then $c_C(p_i)\leq c_C(p_j)$ for any $1\leq i,j \leq k$ and $i\neq j$. So basically, BFS\_C($p$) will output the list of all such nodes which are connected to $p$ and there exists a path from $p$ on which the center-strategicness of nodes are in non-decreasing order.

Let there exists a center-strategic path $P_c(u,v)=\{u_1, u_2, \cdots, u_m \}$, where $u=u_1$ and $u_m=v$, between pair $(u,v)$. The path $p_c$ must have a node $u_x$, where $1\leq x \leq m$ such that $c_C(u_i)\leq c_C(u_j)$, for all $1\leq i,j\leq x$ and $c_C(u_i)\geq c_C(u_j)$, for all $x\leq i,j\leq m$. Thus node $u_x$ must be reachable in the restricted manner from both $u$ and $v$ and will be present in both the list outputs obtained from the procedures BFS\_C($u$) and BFS\_C($v$). Hence all valid center-stategic paths are covered by the algorithm 
\end{proof}
% Then path must follow atlest one of the below given properties.
%\begin{enumerate}
%item $c(u_i)\leq c(u_j)$, for all $1\leq i,j \leq m$ and $i\neq j$.
%\item There exist a node $u_x$, where $1\leq x \leq m$ such that $c(u_i)\leq c(u_j)$, for all %$1\leq i,j\leq x$ and $c(u_i)\geq c(u_j)$, for all $x\leq i,j\leq m$ . 
%\end{enumerate} 
%\end{proof}
\begin{lemma}Time complexity of Algorithm 1 is polynomial in the number of vertices $n$.
\end{lemma} 
\begin{proof}We will analyze the algorithm step by step. Input to the algorithm is a graph with center-strategicness of each node. This can be easily calculated in atmost $O(n^3)$ time using Floyd-Warshall algorithm \cite{m,n}. We can improve this factor to $O(n^2 log~n+mn)$ for sparse graphs using Johnson's algorithm \cite{l}. Now the algorithm's first step takes constant time. Second step is a loop and can be executed atmost $O(n^2)$ times. In the loop we are calling the procedure BFS\_C  two times which takes atmost $O(m+n)$ time. Rest of the steps takes constant time. So, the total time complexity of the algorithm is $O(n^2(m+n))$. So we can check the center-strategicness of graph in $O(n^2(m+n))+O(n^2 log~n+mn)=O(n^2(m+n))$.
\end{proof}
Using lemma 1 and lemma 2 we can conclude that we have an algorithm that decides the center-strategicness of any graph in $O(n^2(m+n))$ time. 
\end{proof}
\subsection{On Erdos-Renyi (ER) Graphs}
In this section, we will describe various results we got on Erdos-Renyi graphs by changing different variables. First we will see various points noted down during results. After then, we will see two different types of plots from the experiment. The below given experimental observations also hold for general graphs.
\begin{enumerate}
\item Initially we suspected that for all the graphs, only one pair of vertices may exist that makes the graph non center-strategic. But from experiments, we found that some of the ER graphs are having more than one such responsible pair of nodes. We also found that there exists just one pair until we are observing the ER graph with atmost $15$ nodes. An ER graph with atleast $16$ nodes may have more than one different pair of nodes between which no center-strategic path exists.
\item We also suspected that all the non center-strategic graphs are planar due to their structure , but from the experiments, we realized that non center-strategic graphs can be both planar as well as non-planar.
\item If a graph is non center-strategic then it is due to the non center-strategicness between the higher degree vertex set. In the experiment, we analyzed that all the vertex pairs which are making the graph non center-strategic are the highest degree vertices or second highest degree vertices or other higher degree vertices from the top.   
\end{enumerate}
Now we will see the experimental results in the form of plots.\\
\textbf{Concentration of CSP vs probability.} Figure. \ref{fig1} is a plot between concentration of Center-Strategic Pairs (CSPs) vs probability $p$. In the experiment, a ER graph of 100 nodes is generated randomly with some probability $p$ which is increasing every time with rate of $.01$ from $0$ to $1$ (X- axis) and the number of CSPs are counted for the corresponding graph generated randomly with probability $p$ ().\\
\begin{figure}[h]
\centering
\subfigure[Concentration of CSP vs probability for graph with 100 nodes]{
\includegraphics[width=5cm, height=6cm]{conc_n100_p01.png}\label{fig1}}\vspace{2mm}
\subfigure[Connected center-strategic graphs vs probability for graph with $100$ nodes]{
\includegraphics[width=5cm, height=6cm]{conf_n100_t10000_p01.png}\label{fig2}}\vspace{2mm}
\subfigure[Connected center-strategic graphs vs probability for graph with $50$ nodes]{
\includegraphics[width=5cm, height=6cm]{conf_n50_t10k_p01.png}\label{fig3}}
\caption[Optional caption for list of figures]{}
\label{fig:subfigureExample}
\end{figure}
\textbf{Connected center-strategic graphs vs probability.} Figure.\ref{fig2} is a plot of  the number of center-strategic ER graph with 100 nodes is generated randomly $10000$ times with some probability $p$ which is increasing every time with the rate of $.01$ from $0$ to $1$ (X- axis) and the number of center-strategic graphs counted out of $10000$ generated graphs of probability $p$ (Y-axis).\\
\textbf{Probability with which a G(n,p) is center-strategic.} As we can see in the Figure.\ref{fig2} the plot at probability $0.10$ we get more than $80\%$ randomly generated center-strategic graphs of $100$ nodes each. For $50$ nodes, it comes in experiment as more than $60\%$ randomly generated graphs are center-strategic after probability $0.10$ as shown in figure.\ref{fig3}.
\subsection{On Trees}
Next we will give a basic definition and we can get the next proposition obviously from the definition.
\begin{definition}
Given a graph $G(V,E)$ and vertices $\alpha,\beta\in V$, by $V_\alpha^{(\beta)}$ 
we mean the set $\{   v\in V : d(\alpha,v)<d(\beta,v) \}$. (By definition, clearly $\alpha \in V_\alpha^{(\beta)}$)
\end{definition}
\begin{proposition}
 Given an undirected tree T(V,E) and given any edge $(\alpha,\beta)\in E$, we have 
$V_\alpha^{(\beta)} \cap V_\beta^{(\alpha)}=\emptyset$
\end{proposition}

\begin{lemma}
\label{main_lemma} 
Given an undirected tree T(V,E) and if for some $x,y,z\in V$, if $(x,y)\in E$ and $(y,z)\in E$
then $V_z^{(y)}\subsetneq V_y^{(x)}$
\end{lemma}
\begin{proof}
Let $u \in V_z^{(y)}  $.
By definition, we know that $d(u,z)<d(u,y)$.
We know that, if T is a connected undirected tree, there exists an unique path between every two vertices. Consider the path between $u$ and $z$. Let us denote this path as $(u,a_1,a_2,\dots,a_k,z)$. Since $(z,y)\in E$, we have either $a_k=y$ or $y\neq a_i, \forall 1\leq i \leq k$. We cannot have $a_k=y$ as in that case $y$ will be closer to $u$ than $z$, which implies that $d(u,z)>d(u,y)$, which is a contradiction. Thus the unique path
connecting $u$ and $y$ has to be $(u,a_1,a_2,\dots,a_k,z,y)$, which is of length $k+2$. Since $(x,y)\in E$, the path connecting $u$ to $x$ must be $(u,a_1,a_2,...,a_k,z,y,x)$ of length $k+3$. This implies that $d(u,x)>d(u,y)$, 
which in turn implies that $u\in V_y^{(x)}$.
$\therefore$ $V_z^{(y)}\subsetneq V_y^{(x)}$. 
The strict containment is because $y\in V_y^{(x)}$ and $y\notin V_x^{(y)}$.
On similar lines, one can prove that $V_x^{(y)}\subsetneq V_y^{(z)} $
\end{proof}

\begin{corollary}
  Given an undirected tree T(V,E) and if for some $x,y,z\in V$, if $(x,y)\in E$ and $(y,z)\in E$
then $|V_z^{(y)}| < |V_y^{(x)}|$ (and $|V_x^{(y)}| < |V_y^{(z)}|$)
\end{corollary}
%\begin{proof}
% Follows from Lemma \ref{main_lemma}
%\end{proof}
\begin{lemma}
Given an undirected tree $T(V,E)$, if for some $x,y\in V$, if $C(x)\leq C(y)$ then 
$|V_x^{(y)}|\geq|V_y^{(x)}|$.
\end{lemma}
\begin{proof}
We know that,
$C(x)=d(x,V_x^{(y)})+ d(x,V_y^{(x)})$ and $C(y)=d(y,V_x^{(y)})+ d(y,V_y^{(x)})$. Clearly, $C(x)=d(y,V_x^{(y)})-|V_x^{(y)}|+d(y,V_y^{(x)})-|V_y^{(x)}|$ so we can write
$C(x)=C(y)+|V_y^{(x)}|-|V_x^{(y)}|$. Given that $C(x)\leq C(y)$, we have $|V_x^{(y)}|\geq|V_y^{(x)}|$.
\end{proof}
\begin{lemma}
Given an undirected tree $T(V,E)$, if for some $x,y,z\in V$, $(x,y)\in E$, $(y,z)\in E$ and 
if $C(x)\leq C(y)$ then $C(y)<C(z)$. 
\end{lemma}
\begin{proof} We know that, $C(z)=d(z,V_z^{(y)})+d(z,V_y^{(z)})$ so we can write $C(z)=d(y,V_z^{(y)})-|V_z^{(y)}|+d(y,V_y^{(z)})+|V_y^{(z)}|$. Also, $C(y)=d(y,V_z^{(y)})+d(z,V_y^{(z)})$ therefore we can get $C(z)-C(y)=|V_y^{(z)}|-|V_z^{(y)}|>  |V_y^{(z)}|  -  |V_y^{(x)}|> |V_x^{(y)} | - |V_y^{(x)} |>0$ by using corollary 1 which infer $C(y)<C(z)$
\end{proof}
\begin{theorem}
 In a tree, the top closeness centrality ranked vertices are at most 2 in number and if two exist then both are adjacent. 
\end{theorem}
\begin{proof}
 First, we prove the later statement by contradiction. Assume that there exist two top closeness centrality ranked vertices and both are not adjacent. Let there are two non-adjacent vertices $u$ and $v$ such that $C(u)=C(v)$, and $\forall x\in V, x\neq u, x\neq v \Rightarrow C(x)>C(u)$. We know that there is an unique path between $u$ and $v$. 
Let the path be ($u,\alpha_1,\alpha_2,...,\alpha_k,v$). Given that $u$ is the top most vertex and that $u$ and $v$ are not adjacent, we have
$C(u)<C(\alpha_1)$. By lemma 5, we have $C(\alpha_1)<C(\alpha_2)<C(\alpha_3)<...<C(\alpha_k)<C(v)$, thus arriving at a contradiction.

Now if there exist more than $2$ vertices with top closeness centrality, then according to the proof given above, they all should be adjacent to each other which is not possible, as it will create cycle in the graph and thus contradict the statement that the given graph is a tree.     
\end{proof}
\begin{theorem}
 In a tree, there is always a center-strategic path between any two vertices. 
\end{theorem}
\begin{proof}
Consider a tree. Let $z$ be the vertex with top closeness centrality. Consider a pair of vertices $u$ and $v$. 
We know that in a tree there is an unique path between every two vertices. Let the path between $u$ and $v$ be 
($u,\alpha_1,\alpha_2,...,\alpha_k,v$). There are two cases, either this path passes through the top ranked vertex $z$
or it doesn't. In case it does, then by lemma 5, it is clear that the vertices on the path connecting $z$ and $u$ and the
path connecting $z$ and $v$, will have $C$ values in non-increasing order, thus yielding a center-strategic path as shown
in the graph $T(V,E)$ in Figure.~\ref{3_v}. In case the path doesn't pass through $z$, then the two paths $u$ to $z$ and $v$ to $z$ intersect as shown 
in the graph $T'(V',E')$ in Figure.~\ref{3_y}. Let the intersection point be $\theta$. Consider the path from $\theta$ to $u$ and $\theta$ to $v$, 
by Lemma. 3, this will have non-increasing values of $C$ which implies that the path is a center-strategic path.

(In Figure.~\ref{3_v} and~\ref{3_y}, the values on each vertex $v$ denotes the reciprocal of closeness centrality value $\frac{1}{C(v)}$)
\end{proof}
%\begin{figure}[h]
%\centering
%\includegraphics[width=.263\textheight]{v.png}
%\caption{$T(V,E)$}
%\label{3_v}
%\end{figure}

%\begin{figure}[h]
%\centering
%\includegraphics[width=.26\textheight]{y.png}
%\caption{$T'(V',E')$}
%\label{3_y}
%\end{figure}
\begin{figure}[h]
\centering
\subfigure[$T(V,E)$]{
\includegraphics[width=.263\textheight, height=7cm]{v.png}\label{3_v}}
\subfigure[$T'(V',E')$]{
\includegraphics[width=.26\textheight, height=7cm]{y.png}\label{3_y}}
\caption[Optional caption for list of figures]{}
\label{fig:subfigureExample}
\end{figure}
\subsection{On Rectilinear Grids} In this section we analyze the navigability in the geographic area which can be mapped to a rectilinear grid. Let us assume that we are given a rectilinear  grid $G$ of size $x\times y$ where all the inner blocks are squares. Then, there are $x$ rows and $y$ columns of blocks in the grid. Nodes are present at the intersection points of the lines that make the grid. The left-uppermost node is denoted by $(0,0)$ and right-lowermost node is represented by $(x,y)$ . A node in a grid is called center if its closeness centrality is greater or equal to all nodes in the grid. 
\begin{lemma} Rectilinear Grids can have either $1$ or $2$ or $4$ centres.   
\end{lemma}
\begin{proof}
We can easily prove the lemma by analyzing the dimension of the grid. If grid is of dimension $x\times y$ then the structures can be categorized into three types on the basis of size number.
\begin{enumerate}
\item $Even \times Even$
\item $Even \times Odd$ or $Odd \times Even$
\item $Odd \times Odd$
\end{enumerate}
In first case when grid is of size $Even \times Even$, the center of the structure will be a single point at node $(\frac{x}{2},\frac{y}{2})$. In second case we will get two nodes with same closeness centrality and they are adjacent. Both centres are located at position $(\frac{x}{2},\lfloor \frac{y}{2} \rfloor)$ and $(\frac{x}{2},\lceil \frac{y}{2}\rceil)$ in the case of $Even \times Odd$ and vice-versa for the other form. In the third and the last case, we will get four centres which are located at vertices of a square and positioned correspondingly to $(\lfloor \frac{x}{2} \rfloor,\lfloor \frac{y}{2} \rfloor )$, $(\lceil \frac{x}{2} \rceil,\lceil \frac{y}{2} \rceil )$, $(\lceil \frac{x}{2} \rceil,\lfloor \frac{y}{2} \rfloor )$ and $(\lfloor \frac{x}{2} \rfloor,\lceil \frac{y}{2}\rceil )$.\end{proof}
\begin{figure}[H]
\begin{center}
\includegraphics[width=10cm, height=3.5cm]{im2.jpg}
\end{center}
\caption{{ An example of all three types of rectilinear grids.}}
\end{figure}


\begin{lemma} Closeness centrality of nodes increases if we move towards any center and decreases if we move away from all the centres. 
\end{lemma}
\begin{figure}[H]
\begin{center}
\includegraphics[width=4cm, height=4cm]{im3.jpg}
\end{center}
\caption{{ An example explaining the lemma and representing closeness centrality by intensity of the node. Black represents highest centrality and white represents the lowest.}}
\end{figure}
\begin{proof} We can easily prove this lemma by observing that when we move away from all centres, two events occur. First that few nodes become closer to us and thus the total distance is reduced by some amount leading to an increase in the closeness centrality. At the same time, rest of the nodes in the grid become farther leading to an increase in the total distance and thus reduce centrality. If we combine the effects of both the events, we will see that the amount of reduction in the total distance is less than the increment in the total distance and thus net effect is the increase in the total distance resulting in a decrement in centrality. Similarly, the other case can be proved. \end{proof}
\begin{theorem}
All rectilinear grids are center-strategic.
\end{theorem}
\begin{proof}
We can easily prove the theorem by using lemma $7$. Suppose, we are given a rectilinear grid $G$ of size $x\times y$. We will show that for any two vertices of $G$, atleast one center-strategic path always exists between them. Let $u$, $v$ are two different vertices of grid $G$. Then by using lemma $7$, we can say that each node $u_$ in the grid has atlest one neighbour vertex $v_i$ having closeness centrality relation $c(u_i)\leq c(v_i)$. It is because, neighbour $v_i$ is more or equal near to a centre node than the current vertex $u_i$.

In the above manner we can always reach from node $u$ to a centre node $c_u$ through a path $P_u=\{u_1, u_2, \cdots, u_s\}$, where $u_1=u$, $u_s=c_u$ and $c(u_i)\leq c(u_{i+1})$ for $1\leq i\leq (s-1)$. In same way we can get a path $P_v=\{v_1, v_2, \cdots, v_t\}$ from node $v$ to a centre node $c_v$, where $v_1=v$, $v_t=c_v$ and $c(v_j)\leq c(v_{j+1})$ for $1\leq j\leq (t-1)$. Now we can have two possibilities. First that both the centre nodes are same, $c_u=c_v$, Second if they are different then by lemma $6$, there may exist either $1$ or $2$ or $4$ centres and in all three cases either they are adjacent to each other or can be connected through another centre $c_k$. So for all pair of vertices $(u,v)$, we can get a path $P$ between $u$ and $v$ which is the concatenation of the path $P_u$, $\{c_u, c_k, c_v\}$ and the path in the inverse direction of $P_v$ such that  $P=\{u, u_2, \cdots ,c_u, c_k, c_v, \cdots, v_2, v\}$. If we will analyze the closeness centrality of vertices in $p$, then we will find one minima (the centre nodes) and the path fulfils the requirement of being center-strategic path. 

Thus in grid $G$ between each pair we can find such path hence all rectilinear grids are center-strategic.
\end{proof}

\section{Conclusion} Navigability of a graph plays an important role for human or robot to navigate in a new environment. In this paper, we gave a polynomial time heuristic to verify the navigability of any connected graph. With a small change in algorithm we can easily quantify the degree of navigability of any graph. Using this heuristic we experimented ER graphs and produced some novel results. We analysed that trees and rectilinear grids are special graphs which are always easily navigable. Question to improve the time complexity of navigability is still open. Also the claim that each non center-strategic graph contains atleast one complete bipartite graph $K_{3,2}$ with some additional constraints, is still a conjecture.

\bibliographystyle{plain}
\begin{thebibliography}{9}
\bibitem{a} A. Bavelas, Human Organization, Vol. 7 (1948), pp. 16-30.

\bibitem{b} H. J. Leavitt, Some effects of certain communication patterns on group performance. Journal of Abnormal and Social Psychology, Vol. 46, No. 1. (January 1951), pp. 38-50. 

\bibitem{k} Edward F. Moore. The shortest path through a maze. In Proceedings of the International Symposium on the Theory of Switching, pages 285–292. Harvard University Press, 1959.

\bibitem{er} {P. Erdos and A Renyi}, {On the Evolution of Random Graphs}, {Publication of the Mathematical Institute of the Hungarian Academy of Sciences}, 17--61, 1960.

\bibitem{m} Robert W. Floyd. Algorithm 97 (SHORTEST PATH). Communications of the ACM,
5(6):345, 1962.

\bibitem{n} Stephen Warshall. A theorem on boolean matrices. Journal of the ACM, 9(1):11–12, 1962. 

\bibitem{j} S. Milgram. The Small World Problem. Psychology Today, 1:61–67, 1967.

\bibitem{l} Donald B. Johnson. Efficient algorithms for shortest paths in sparse networks. Journal of the ACM, 24(1):1–13, 1977.

\bibitem{c} Linton C. Freeman, Centrality in social networks conceptual clarification Social Networks, Vol. 1, No. 3. (January 1978), pp. 215-239.


\bibitem{e} David Eppstein, Joseph Wang, Fast approximation of centrality In SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms (2001), pp. 228-229.

\bibitem{d} Kazuya Okamoto, Wei Chen, Xiang-Yang Li edited by Franco P. Preparata, Xiaodong Wu, Jianping Yin, Ranking of Closeness Centrality for Large-Scale Social Networks Frontiers in Algorithmics In Frontiers in Algorithmics , Vol. 5059 (2008), pp. 186-195.

\bibitem{i} F. F. Dragan and M. Matamala. Navigating in a graph by aid of its spanning tree metric. 25(1):306–332, 2011.

\bibitem{gg} S. D. Moeser. Cognitive mapping in a complex building. Environment and Behavior, 20:21–49, 1988.

\bibitem{aa} V Aginsky, C Harris, R Rensink, and J Beusmans. Two strategies for learning a route in a driving simulator. Environmental Psychology, 17:317–331, 1997.

\bibitem{bb} R. A. Hart and G. T. Moore. Image and environment: Cognitive mapping and spatial behaviour. Basic Books, 1973.

\bibitem{cc} T.P. McDonald and J. W. Pellegerino. Psychological perspectives on spatial cognition. Advances in psychology, 96:47–82, 1993.

\bibitem{dd} G. T. Moore and R. G. Golledge. Environmental knowing. Hutchinson and Ross, 1976.

\bibitem{ee} Aysu Baskaya, Christopher Wilson, and Yusuf Ziya zcan. Wayfinding in an unfamiliar environment. Environment and Behavior, 36:839–867, 2004.

\bibitem{ff} R. Passini. Spatial representations, a wayfinding perspective. Environmental Psychology, 4:153–164, 1984.

\bibitem{f} Sudarshan Iyengar, S. R. and Veni Madhavan, C. E. and Zweig, Katharina A. and Natarajan, Abhiram, 
\emph{ Understanding Human Navigation Using Network Analysis}, Topics in Cognitive Science, 4(1), 121--134, 2012.

\bibitem{g} Ramesh, A.; Ramesh, S.; Iyengar, S.; Sekhar, V.; Rangan, C.P., "Obstacles Incentivize Human Learning: A Network Theoretic Study," Advances in Social Networks Analysis and Mining (ASONAM), 2012 IEEE/ACM International Conference on , vol., no., pp.1295,1300, 26-29 Aug. 2012.

\bibitem{h} Vijesh, M.; Iyengar, S.; Vijay Mahantesh, S.M.; Ramesh, A.; Pandurangan, C.; Madhavan, V., "A Navigation Algorithm Inspired by Human Navigation," Advances in Social Networks Analysis and Mining (ASONAM), 2012 IEEE/ACM International Conference on , vol., no., pp.1309,1314, 26-29 Aug. 2012.

\end{thebibliography}
\end{document}

